Search results for "Continuous knapsack problem"
showing 5 items of 5 documents
Learning automata-based solutions to the optimal web polling problem modelled as a nonlinear fractional knapsack problem
2011
We consider the problem of polling web pages as a strategy for monitoring the world wide web. The problem consists of repeatedly polling a selection of web pages so that changes that occur over time are detected. In particular, we consider the case where we are constrained to poll a maximum number of web pages per unit of time, and this constraint is typically dictated by the governing communication bandwidth, and by the speed limitations associated with the processing. Since only a fraction of the web pages can be polled within a given unit of time, the issue at stake is one of determining which web pages are to be polled, and we attempt to do it in a manner that maximizes the number of ch…
A genetic algorithm for the minimum generating set problem
2016
Graphical abstractDisplay Omitted HighlightsWe propose a novel formulation for the MGS problem based on multiple knapsack.The so-conceived MGS problem is solved by a novel GA.The GA embeds an intelligent construction method and specialized crossover operators.We perform a thorough comparison with regards to state-of-the-art algorithms.The proposal proves to be very competitive, specially for large and hard instances. Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinat…
Learning Automata-Based Solutions to Stochastic Nonlinear Resource Allocation Problems
2009
“Computational Intelligence” is an extremely wide-ranging and all-encompassing area. However, it is fair to say that the strength of a system that possesses “Computational Intelligence” can be quantified by its ability to solve problems that are intrinsically hard. One such class of NP-Hard problems concerns the so-called family of Knapsack Problems, and in this Chapter, we shall explain how a sub-field of Artificial Intelligence, namely that which involves “Learning Automata”, can be used to produce fast and accurate solutions to “difficult” and randomized versions of the Knapsack problem (KP).
A Hierarchy of Twofold Resource Allocation Automata Supporting Optimal Sampling
2009
We consider the problem of allocating limited sampling resources in a "real-time" manner with the purpose of estimating multiple binomial proportions. More specifically, the user is presented with `n ' sets of data points, S 1 , S 2 , ..., S n , where the set S i has N i points drawn from two classes {*** 1 , *** 2 }. A random sample in set S i belongs to *** 1 with probability u i and to *** 2 with probability 1 *** u i , with {u i }. i = 1, 2, ...n , being the quantities to be learnt. The problem is both interesting and non-trivial because while both n and each N i are large, the number of samples that can be drawn is bounded by a constant, c . We solve the problem by first modelling it a…
On Utilizing Stochastic Non-linear Fractional Bin Packing to Resolve Distributed Web Crawling
2014
This paper deals with the extremely pertinent problem of web crawling, which is far from trivial considering the magnitude and all-pervasive nature of the World-Wide Web. While numerous AI tools can be used to deal with this task, in this paper we map the problem onto the combinatorially-hard stochastic non-linear fractional knapsack problem, which, in turn, is then solved using Learning Automata (LA). Such LA-based solutions have been recently shown to outperform previous state-of-the-art approaches to resource allocation in Web monitoring. However, the ever growing deployment of distributed systems raises the need for solutions that cope with a distributed setting. In this paper, we prese…